package LeetCode_142;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/30 7:51
 * 142.环形链表 II
 *
 */

  class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //设起始节点 到 入环节点 距离为 S，慢指针环内位移为 L ，环长 C
        //（快指针一次 两步，所以慢指针位移*2==快指针位移；快慢指针相遇，则快指针比慢指针快一圈）
        //有： (S+L) * 2 = S + C + L
        //推得： S = C - L  则设起始节点 到 入环节点 距离 == 相遇点 到 入环节点
        ListNode fast = head;
        ListNode slow = head;

        while (true){
            if (fast==null){
                break;
            }
            fast = fast.next;
            slow = slow.next;
            if (fast==null){
                break;
            }
            fast = fast.next;
            if (fast==slow){
                break;
            }
        }
        if (fast==null){
            return null;
        }
        while (fast != head){
            fast= fast.next;
            head = head.next;
        }
        return fast;
    }
}